//public class DAY0318 {
//    public void setZeroes(int[][] matrix) {
//        int m = matrix.length, n = matrix[0].length;
//        boolean[] row = new boolean[m];
//        boolean[] col = new boolean[n];
//        for (int i = 0; i < m; i++) {
//            for (int j = 0; j < n; j++) {
//                if (matrix[i][j] == 0) {
//                    row[i] = col[j] = true;
//                }
//            }
//        }
//        for (int i = 0; i < m; i++) {
//            for (int j = 0; j < n; j++) {
//                if (row[i] || col[j]) {
//                    matrix[i][j] = 0;
//                }
//            }
//        }
//    }
//
//    public boolean isValidSudoku(char[][] board) {
//        int[][] rows = new int[9][9];
//        int[][] columns = new int[9][9];
//        int[][][] subboxes = new int[3][3][9];
//        for (int i = 0; i < 9; i++) {
//            for (int j = 0; j < 9; j++) {
//                char c = board[i][j];
//                if (c != '.') {
//                    int index = c - '0' - 1;
//                    rows[i][index]++;
//                    columns[j][index]++;
//                    subboxes[i / 3][j / 3][index]++;
//                    if (rows[i][index] > 1 || columns[j][index] > 1 || subboxes[i / 3][j / 3][index] > 1) {
//                        return false;
//                    }
//                }
//            }
//        }
//        return true;
//    }
//
//    public int firstBadVersion(int n) {
//        int left=1,right=n;
//        while(right>left){
//            int mid=(right-left)/2+left;
//            if(isBadVersion(mid)){
//                right=mid;
//            }else{
//                left=mid+1;
//            }
//        }return left;
//    }
//
////    private boolean isBadVersion(int mid) {
////    }
//
//    public int[] searchRange(int[] nums, int target) {
//        int leftIdx = binarySearch(nums, target, true);
//        int rightIdx = binarySearch(nums, target, false) - 1;
//        if (leftIdx <= rightIdx && rightIdx < nums.length && nums[leftIdx] == target && nums[rightIdx] == target) {
//            return new int[]{leftIdx, rightIdx};
//        }
//        return new int[]{-1, -1};
//    }
//
//    public int binarySearch(int[] nums, int target, boolean lower) {
//        int left = 0, right = nums.length - 1, ans = nums.length;
//        while (left <= right) {
//            int mid = (left + right) / 2;
//            if (nums[mid] > target || (lower && nums[mid] >= target)) {
//                right = mid - 1;
//                ans = mid;
//            } else {
//                left = mid + 1;
//            }
//        }
//        return ans;
//    }
//
//}
